#ifndef BIT_H_
#define BIT_H_

#include <cmath>
#include <cstddef>
#include <cstdint>
#include <string>
#include <type_traits>


namespace lxj
{

inline std::string getNumBinary(int a)
{
    std::string binary;
    binary.reserve(32);
    for (int i = 31; i >= 0; i--) {
        char c = ((a & (1 << i)) != 0) ? '1' : '0';
        binary.push_back(c);
    }
    return binary;
}

// 力扣231 判断数字n是否是2的幂
template<class T, std::enable_if_t<std::is_integral_v<T>, int> = 0>
inline constexpr bool is2power(T n)
{
    return n > 0 && n == (n & -n);
}

// 力扣231 判断数字n是否是3的幂
template<class T, std::enable_if_t<std::is_integral_v<T>, int> = 0>
inline constexpr bool is3power(T n)
{
    int64_t max_3 = 4052555153018976267;
    return n > 0 && max_3 % n == 0;
}

// 力扣342 判断数字n是否是4的幂
inline constexpr bool is4power(int n)
{
    bool b = false;
    if (n > 0 && n == (n & -n)) {
        b = (long)std::log2(n) % 2 == 0 ? true : false;
    }
    return b;
}

// 返回 >=n 的最小的2的幂
inline constexpr long near2power(int n)
{
    if (n <= 0) return 1;
    n--;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    return n + 1;
}

// 给你两个整数left和right,表示去加[left,right]
// 返回此区间内所有数字 & 的结果
inline constexpr int range_bitwise_and(int left, int right)
{
    while (left < right) {
        right -= (right & -right);
    }
    return right;
}

// 力扣190 反转数字n的二进制状态，不是0->1 || 1->0，而是逆序
inline constexpr int reverse_bits(int n)
{
    n = ((n & 0xaaaaaaaa) >> 1) | (n & 0x55555555) << 1;
    n = ((n & 0xcccccccc) >> 2) | (n & 0x33333333) << 2;
    n = ((n & 0xf0f0f0f0) >> 4) | (n & 0x0f0f0f0f) << 4;
    n = ((n & 0xff00ff00) >> 8) | (n & 0x00ff00ff) << 8;
    n = ((n & 0xffff0000) >> 16) | (n & 0x0000ffff) << 16;
    return n;
}

// 力扣461 返回一个二进制中有几个1
inline constexpr size_t banary1count(int n)
{
    /* size_t ans = 0;
    while (n != 0) {
        int right1 = n & -n;
        n -= right1;
        ans++;
    }
    return ans; */

    n = (n & 0x55555555) + (n >> 1 & 0x55555555);
    n = (n & 0x33333333) + (n >> 2 & 0x33333333);
    n = (n & 0x0f0f0f0f) + (n >> 4 & 0x0f0f0f0f);
    n = (n & 0x00ff00ff) + (n >> 8 & 0x00ff00ff);
    n = (n & 0x0000ffff) + (n >> 16 & 0x0000ffff);
    return n;
}

}   // namespace lxj

#endif